package org.example.Soution001;

public class FindKthLargestQuickSort {
    public static void main(String[] args) {
        int[] nums = new int[]{3,2,1,5,6,4};
        FindKthLargestQuickSort obj = new FindKthLargestQuickSort();
        System.out.println(obj.findKthLargest(nums, 2));
    }

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickSort(nums,0,n-1,n-k);
    }

    public int quickSort(int[] nums, int l, int r, int k) {
        if(l==r){
            return nums[k];
        }
        int x=nums[l],i=l-1,j=r+1;
        while(i<j) {
            do i++; while(nums[i]<x);
            do j--; while(nums[j]>x);
            if(i<j){
                swap(nums,i,j);
            }
        }
        if(k<=j) return quickSort(nums,l,j,k);
        else return quickSort(nums,j+1,r,k);

    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
